// 新开一行，防止代码拼接连在一起
#ifndef COMPILE_TEST // 后期在执行compile程序替换时带上-D COMPILE_TEST
#include "header.cpp"
#endif

class Answer
{
public:
    bool wordBreak(string s, vector<string> &wordDict)
    {
        // 以i位置为结尾时的串能否利用字典拼接出
        // 用于倒着遍历
        int n = s.size();
        vector<bool> dp(n + 1, false);
        dp[0] = true;
        // 将字典中的所有单词存起来
        unordered_set<string> exit;
        for (auto s : wordDict)
        {
            exit.insert(s);
        }
        // 填表
        s = ' ' + s;
        string tmp;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (dp[j] == true && exit.count(s.substr(j + 1, i - j)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

void test_1()
{
    vector<string> vs = {"leet", "code"};
    bool ret = Solution().wordBreak("leetcode", vs);
    if (ret == Answer().wordBreak("leetcode", vs))
    {
        cout << "测试用例1通过" << endl;
    }
    else
    {
        cerr << "测试用例1没通过" << endl;
    }
}
void test_2()
{
    vector<string> vs = {"apple", "pen"};
    bool ret = Solution().wordBreak("penapple", vs);
    if (ret == Answer().wordBreak("penapple", vs))
    {
        cout << "测试用例2通过" << endl;
    }
    else
    {
        cerr << "测试用例2没通过" << endl;
    }
}
void test_3()
{
    vector<string> vs = {"apple", "cats", "dog", "sand", "and", "cat"};
    bool ret = Solution().wordBreak("catscatandsandog", vs);
    if (ret == Answer().wordBreak("catscatandsandog", vs))
    {
        cout << "测试用例3通过" << endl;
    }
    else
    {
        cerr << "测试用例3没通过" << endl;
    }
}
int main()
{
    test_1();
    test_2();
    test_3();

    return 0;
}